1 Contenido de la clase
Divide y vencerás: definición y características
La técnica de divide y vencerás consiste en dividir un problema en problemas más pequeños y simples hasta encontrar una solución trivial o conocida; la solución al problema general es la unión o combinación de las soluciones parciales de cada problema pequeño.
Características que debe tener un problema P (con solución S) para poder aplicar la técnica:
- El problema P se puede dividir en problemas pi.
- Cada pi es similar y más simple (de complejidad menor) que el problema original.
- Cada pi se puede resolver con esta misma técnica de manera recursiva.
- Cada pi tiene una solución si.
- La solución S del problema inicial P se obtiene a partir de la unión o combinación de cada solución si.
Consideraciones: la técnica asume que existe una solución y encuentra solo una; la operación de unión o combinación de las soluciones depende de la naturaleza de cada problema y debe ser eficiente. El material remite al diagrama del algoritmo en el documento Algoritmo BackTracking y Divide-Venceras.pdf.
Ejemplos de divide y vencerás
- Algoritmo de ordenación QuickSort.
- Búsqueda binaria en una lista ordenada.
- Multiplicación de dos números muy grandes.
En algunos casos, la solución si de cada subproblema pi se puede resolver en forma concurrente.
QuickSort
Definición del algoritmo en notación de Haskell (programación declarativa):
ordenaQS (x:xs) = ordenaQS (menores) ++ [x] ++ ordenaQS (mayores)
where menores = [ e | e <- xs, e < x ]
mayores = [ e | e <- xs, e >= x ]
ordenaQS [] = []
Se toma un elemento como pivote (el primero, x), se separan los menores y los mayores, se ordenan recursivamente ambas partes y se concatenan (++) con el pivote en medio. La lámina remite a la implementación en Qsort.pas y sugiere ver el código Haskell y comparar los paradigmas de programación.
Búsqueda binaria en una lista ordenada
Pseudo-código recursivo de la lámina (Binario(Izq, Der, X)):
- Si Izq < Der: se calcula Med = (Izq + Der) / 2.
- Si X > Elem[Med], se busca recursivamente en Binario(Med, Der, X); si no, se busca en Binario(Izq, Med, X).
- Si no (Izq = Der): si X = Elem[Izq], se imprime "Encontrado en la posición Izq"; si no, "El elemento buscado no está".
Se muestra además la implementación en Pascal (function BusquedaBinaria(...)), que compara con el pivote DAT[pivote] y recorre recursivamente el intervalo adecuado; si no lo encuentra, devuelve −1.
Multiplicación de dos números muy grandes
Problema: encontrar un algoritmo para multiplicar dos números enteros muy grandes (ejemplo de la lámina: 3272362332323 × 8876867324324), usando divide y vencerás.
Solución (idea): si u y v son dos números de n dígitos, se descomponen respecto a 10^s, donde s es la parte entera de n/2:
- u = 10^s · w + x (w es el cociente y x el resto).
- v = 10^s · y + z (y es el cociente y z el resto).
Entonces: u · v = (10^s · w + x) · (10^s · y + z) = 10^(2s) · w·y + 10^s · (w·z + x·y) + x·z.
Se calculan las suboperaciones w·y, w·z, x·y y x·z: si los operandos son "pequeños" se multiplican de la forma clásica; si son "muy grandes" se aplica de nuevo el algoritmo (recursión). El algoritmo (Fun Mult(u, v)) toma n = Max(tamaño(u), tamaño(v)); si n es pequeño regresa la multiplicación clásica; si no, con s = n div 2 calcula w = u div 10^s, x = u mod 10^s, y = v div 10^s, z = v mod 10^s y regresa Mult(w, y)·10^(2s) + 10^s·(Mult(w, z) + Mult(x, y)) + Mult(x, z). La lámina desarrolla el ejemplo numérico 56781 × 81765 = (567·10^2 + 81) × (817·10^2 + 65), descomponiendo recursivamente cada producto.
Backtracking (vuelta atrás, depth-first)
El backtracking es un método sistemático que itera a través de todas las combinaciones posibles de búsqueda de solución. Puede encontrar todas las soluciones existentes, la primera o la mejor, o establecer que no hay solución, de manera sistemática y organizada: realiza una búsqueda completa y exhaustiva.
Es un algoritmo basado en prueba y error, por lo que en general puede no ser muy eficiente y puede tomar mucho tiempo encontrar una solución. Para llegar a una solución (la mejor o todas) es necesario pasar por una serie de decisiones adecuadas: la solución se construye por etapas, partiendo de una solución parcial. Se aplica en problemas donde existe un conjunto de soluciones y el orden en encontrarlas no importa.
Origen histórico del backtracking
La técnica tiene su origen en los años 50 por el matemático Derrick Henry Lehmer (Universidad de California, Berkeley) y fue formalizada en los años 60 por R. J. Walker, Solomon Wolf Golomb y Leonard D. Baumert.
Árbol de búsqueda y condiciones de aplicación
El material muestra el árbol de búsqueda del algoritmo de backtracking: las soluciones parciales se ramifican con las decisiones posibles y las ramas que no llevan a una solución se abandonan. Un problema debe cumplir para aplicar backtracking:
- Existe una forma de saber si una solución encontrada es o no correcta.
- Existe una forma de generar soluciones parciales.
- El problema ofrece un conjunto de decisiones para generar las posibles soluciones parciales.
Algoritmo de backtracking
- Elegir una solución parcial del conjunto inicial de opciones de solución (triviales).
- Acompletar la solución parcial con base en las decisiones o reglas del problema, para construir la solución final u otra solución parcial (el estado final es la terminación del problema o la solución completa).
- Si esta es una solución, terminar.
- Si no, aplicar de nuevo el primer paso.
- Si no se puede acompletar la solución parcial (ya no hay más posibilidades), considerar otra alternativa de solución parcial del primer paso e ir al segundo paso.
La lámina remite de nuevo al documento Algoritmo BackTracking y Divide-Venceras.pdf.
2 Puntos destacados / Lo que hay que saber
3 Actividades y tareas pendientes
No se dejó en esta clase una tarea con fecha de entrega.
4 Dudas que podrían examinar
¿Qué es divide y vencerás?
Dividir el problema en subproblemas más pequeños y simples; resolver cada uno con la misma técnica (recursivamente) hasta un caso trivial y combinar las soluciones parciales para obtener la solución general.
¿Qué condiciones debe cumplir un problema para aplicar divide y vencerás?
Que sea divisible en subproblemas similares y más simples, que cada uno se pueda resolver recursivamente y que la unión de las soluciones parciales dé la solución general.
¿Cuántas soluciones encuentra divide y vencerás?
Asume que existe una solución y encuentra solo una.
¿Cómo funciona el quicksort en Haskell?
Toma un pivote (la cabeza x), forma la lista de los menores y la de los mayores respecto al pivote, las ordena recursivamente y concatena: menores ++ [x] ++ mayores.
¿Cómo se multiplican dos números muy grandes con divide y vencerás?
Descomponiendo cada número en cociente y resto respecto a 10^s: u = 10^s·w + x y v = 10^s·y + z; entonces u·v = 10^(2s)·w·y + 10^s·(w·z + x·y) + x·z, multiplicando recursivamente los productos parciales.
¿Qué es el backtracking?
Un método de búsqueda completa y exhaustiva (prueba y error) que recorre sistemáticamente las combinaciones posibles para encontrar una, todas o la mejor solución, o para establecer que no hay solución.
¿Por qué el backtracking puede ser poco eficiente?
Porque explora combinaciones por prueba y error y puede tomar mucho tiempo encontrar una solución.
¿Quién originó el backtracking?
Lehmer (años 50, Universidad de California, Berkeley); fue formalizado en los años 60 por Walker, Golomb y Baumert.
¿Qué es una solución parcial?
Un estado de la solución que se construye por etapas, a partir del cual se toman decisiones (reglas del problema) para completar la solución final.
5 Sitios o recursos para visitar
- QuickSort — algoritmo de ordenación por pivote (divide y vencerás) (dominio: google.com).
- Búsqueda binaria — búsqueda sobre listas ordenadas por descarte de mitades (dominio: google.com).
- Multiplicación de números muy grandes — técnica para multiplicar números de muchos dígitos con divide y vencerás (dominio: google.com).
- Backtracking (vuelta atrás) — técnica de búsqueda exhaustiva en profundidad (dominio: google.com).
- Haskell (GHC) — lenguaje declarativo en el que se expresa el quicksort en pocas líneas (dominio: haskell.org).
6 Glosario de términos
- Divide y vencerás: técnica que divide el problema en subproblemas más pequeños y simples, los resuelve recursivamente y combina sus soluciones
- Combinación (unión): operación que une las soluciones parciales para formar la solución general; depende de la naturaleza del problema
- Quicksort: algoritmo de ordenación recursivo basado en un pivote: menores + pivote + mayores
- Pivote: elemento que se toma como referencia para separar los menores de los mayores
- Búsqueda binaria: búsqueda en una lista ordenada que compara con el elemento central y descarta la mitad correspondiente en cada llamada recursiva
- Comprensión de listas: notación de Haskell ([ e | e <- xs, e < x ]) para construir listas con una condición
- Multiplicación de números muy grandes: problema de multiplicar enteros de muchos dígitos descomponiéndolos como u = 10^s·w + x
- Backtracking (vuelta atrás): método de búsqueda en profundidad, completo y exhaustivo, basado en prueba y error
- Búsqueda exhaustiva: recorrido sistemático de todas las combinaciones posibles de búsqueda
- Solución parcial (backtracking): solución en construcción, formada por etapas mediante decisiones adecuadas
- Decisión adecuada: elección, entre las que ofrece el problema, que permite completar una solución parcial
- Estado final: terminación del problema o solución completa en el algoritmo de backtracking
7 Mapa mental textual
- Programación Avanzada · Clase 2 — Divide y vencerás y backtracking
- Divide y vencerás
- Dividir en subproblemas pequeños y simples · resolver cada uno recursivamente · combinar
- Consideraciones: asume solución única · combinación eficiente y dependiente del problema
- Ejemplos: quicksort · búsqueda binaria · multiplicación de números muy grandes
- Subproblemas independientes → resolución concurrente
- Quicksort
- Haskell: pivote + menores ++ [x] ++ mayores (recursivo)
- Comparar con Qsort.pas (imperativo)
- Búsqueda binaria
- Comparar con el elemento medio · recursión por la mitad derecha o izquierda
- Implementación en Pascal (devuelve −1 si no está)
- Multiplicación de números muy grandes
- u = 10^s·w + x · v = 10^s·y + z
- u·v = 10^(2s)·w·y + 10^s·(w·z + x·y) + x·z
- Clásica si es pequeño · recursiva si es muy grande (s = n div 2)
- Backtracking (vuelta atrás, depth-first)
- Búsqueda completa y exhaustiva · prueba y error · puede ser poco eficiente
- Encuentra todas / la primera / la mejor · o establece que no hay
- Construcción por etapas con decisiones · soluciones parciales
- Origen: Lehmer (años 50) · Walker, Golomb y Baumert (años 60)
- Condiciones: verificar soluciones · generar parciales · decisiones
- Árbol de búsqueda
- Algoritmo: elegir parcial → acompletar → ¿solución? → retroceder a otra alternativa
- Divide y vencerás